package com.arron.algorithm.leetcodetop100.二叉树;


import com.arron.algorithm.tree.TreeNode;

import java.util.*;

/**
 * leetcode  94. 二叉树的中序遍历
 *
 */
public class TreeTraverse {



    //二叉树的前序遍历，迭代使用栈 根--》左--》右
    public List<Integer> firstOrder(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<Integer> res = new ArrayList<>();
        //前序遍历
        while (!stack.isEmpty()){

            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.right!=null){
                stack.push(pop.right);
            }
            if (pop.left !=null){
                stack.push(pop.left);
            }

        }
        return res;
    }

    public static void main(String[] args) {
        // 构建二叉树:       1
        //                / \
        //               2   3
        //              / \
        //             4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        TreeTraverse traversal = new TreeTraverse();
        List<Integer> result = traversal.firstOrder(root);
        System.out.println(result);  // 输出: [1, 2, 4, 5, 3]
    }



    //二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {


        List<List<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> z = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                z.add(poll.val);
                if (poll.left !=null){

                    queue.offer(poll.left);
                }

                if (poll.right !=null){
                    queue.offer(poll.right);
                }
            }
            res.add(z);

        }


        return res;
    }




    /**
     * 使用Morris遍历实现 树的先序遍历 空间复杂度为O(1)
     */
    public List<Integer> preTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();

        TreeNode cur = root;
        TreeNode mostRight = null;

        while (cur != null){
            //判断当前节点是否有左树
            if (cur.left!=null){
                //寻找最右节点
                mostRight = cur.left;
                while (mostRight.right != cur && mostRight.right!=null){
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null){
                    //第一次找到自己，打印
                    res.add(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                }
                if (mostRight.right == cur){
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else {
                res.add(cur.val);
                //没有左树 直接向右移动
                cur = cur.right;
            }

        }
        return res;
    }

    /**
     * 使用Morris遍历实现 树的中序遍历 空间复杂度为O(1)
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();

        TreeNode cur = root;
        TreeNode mostRight = null;

        while (cur != null){
            //判断当前节点是否有左树
            if (cur.left!=null){
                //寻找最右节点
                mostRight = cur.left;
                while (mostRight.right != cur && mostRight.right!=null){
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }
                if (mostRight.right == cur){
                    //第二次回到自己位置时打印
                    res.add(cur.val);
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else {
                //没有左树 直接打印
                res.add(cur.val);
                //没有左树 直接向右移动
                cur = cur.right;
            }

        }
        return res;
    }


}
